The Construction of Missile Guidance Codes Resistant to Random Interference By A. R. ECKLER (Manuscript received February 8, 1960) Many types of missiles are guided by a finite set of distinct commands radioed from the ground in the form of a time-sequence of rf pulses. The command information is contained in the n — 1 time spacings between successive pulses in a group of size n, and is encoded and decoded by means of muUiiapped delay lines combined with and gates. This paper discusses the problem of encoding command information (i.e., selecting the tim-e spac- ings between pulses) so that m false pulses (m ^ n — 2) cannot combine with the n true pulses in any way to form a false command. Although it is very easy to state the restrictions that must be imposed on the time spacings between the pulses in the different commands, no general methods exist for finding, among codes satisfying these restrictions, those codes in which the longest command is as short as possible. This paper presents certain lower hounds, together with a few empirically derived codes approaching these lower bounds. The relationship between these codes and the well-known error-correcting binary codes of information theory is discussed in an ap- pendix. I. INTRODUCTION Many types of missiles are guided by commands consisting of a time sequence of rf pulses. The missile receiver is capable of receiving not only the true command pulses, I)ut also any interfering rf pulses emanat- ing from other radars in the vicinity (friendly interference) or deliber- ately generated by the enemy (enemy interference). The purpose of this paper is to suggest command-encoding methods that minimize the effects of this interference. Greatest emphasis is placed on random interference models, because it is difficult to make realistic general as- sumptions about the behavior of an enemy \vh(t knows something about the code structure. The following sections may convey the impression that the construc- 973 974 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 tion of a code invulnerable to random pulse interference is the only factor entering into the choice of a code. This is not meant to be the case; ac- curacy and reliability of decoding e(iuipnient, weight in the missile receiver, power considerations at the transmitter and missile dynamics and maneuverabihty also play very important roles. However, it will be made clear to the reader that code invulnerability should not be completely ignored, and that reas<)nai)le guideposts of dfesigii are avail- able. In order to fix ideas, the codes presented in this paper are discussed in terms of missile guidance. However, the reader will note that other applications are possible. In particular, the codes described here can be used in radio communications to provide protection against the mutual interference of many communications transmitters operating in the .same area on the same frequency. 1.1 The Engineering Background of the Problem In many missile guidance systems, command information is sent to the missile by means of rf pulses. Specifically, the information is con- tained in the time spacings between successive pulses in a group of two or more pulses. Successive groups of pulses are spaced much more widely apart becau.sc of average power limitations on the magnetron. There are many physical devices suitable for encoding and decoding commands. This paper discusses a typical device for encoding discrete commands, such as "yaw left one unit" or "pitch down one unit." These commands are added up in the missile receiver until the desired correc- tion has been achieved. Discrete commands can also be used for such functions as turning rocket motors on or off or destroying the missile. A discrete command is conveniently decoded in the missile receiver by means of a lumped -parameter or distributed-parameter delay Hne tapped at several points (see Fig. 1). The earlier pulses in an incoming sequence are delayed the correct amounts by the delay line m order that the inputs to the and gate be simultaneously activated. In practice, it is sufficient that the several and gate inputs be activated within a short time interval. Let t denote the maximum possible range of input times (i.e., the difference in time between the earliest and latest input) that still activates the and gate. Because of r (which is called the discrete command tolerance), one must be careful not to let two distinct commands have similar encodings. It is shown hi the Appendix that an adeciuatc separation of different commands is always achieved if one assigns time spacings in integral multiples of the discrete command tolerance t. MISSILE GUIDANCE CODES DELAY LINE OF MISSILE RECEIVER 975 INCOMING PULSES - t, - YAW-LEFT DISCRETE COMMAND ENCODED AS \i±A PITCH-DOWN DISCRETE COMMAND ENCODED AS A Fig. 1 — Method of decoding discrete command by means of distributed- parameter delay line tapped at several points. It is clear that only t wo pulses arc needed to encode a command. How- ever, in order to obtain a greater degree of security against false pulses, it is necessary to use three or more pulses per command. The mathe- matical problem discussed in this paper is the construction of such security codes. The same delay line and and gate can be used in the communications problem already menlioned. Here the group of pulses plays the role of an address code rather than a command. Each communications trans- mitter uses a specific address code as a generalized "pulse" with which to communicate information; thus, different transmitters can use the same frequency witliout interfering with each other. 1.2 A Criterion for Judging Code Effectiveness The invulnerability of codes to false pulses is measured by the follow- ing simple criterion : the maximum number of false pulses that cannot interfere with a code group (either by changing the position of a com- mand or producing a diiTerent conmiand), no matter how these false pulses are placed in time with respect to the true code group. This criterion permits only a rough ordering of codes with respect to invuhierability ; redundancy of orders and clo.sed-loop missile response also play an obvious role. However, it does focus attention on a very important factor. No matter what random interfeience model is postu- jated — for example, a PoLsson process of random pulses, a set of radars with approximately the same pulse repetition frequency operating inde- 976 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 pendently of each other, or peaks of random gaussian noise having aver- age po\vcr a certain number of decibels Ijclow the pulse recognition threshold — false single pulses per unit time are much more frequent than false pairs having a particular spacing, false pairs are much more frequent than false triples, and so on. This situation is especially true when the discrete command tolerance t is small with respect to the average time between false pulses. II. ONE-STAGE CODES This section discusses the problem of constructing one-stage codes (that is, codes using a delay line and and circuit) for a set of k distinct commands. Each encoded command consists of a sot of n pulses; the command information is contained in the (n — 1) time spacings between pairs of successive pulses. One can encode these /.■ commands such that i false pulses cannot combine m any way with (n — i) pulses from any command to form either the same command (shifted in time) or one of the other (k -~ 1) commands. The maximum possible value of i is equal to (n — 2), because (n — 1) false pulses can combine with one ti-ue pulse to form false commands in many different ways. We first discuss methods of encoding commands invulnerable to (n — 2) false pulses; later this restriction is relaxed to fewer pulses. 2.1 The Construction of One-Stage Codes with Maximum Protection It may be helpful to think about a specific coding problem while reading this section. Let us assume that we wish to encode two commands (k = 2) consistuig of three pulses each (n = 3); by suitable encoding we can insure that a single false pulse {n — 2 = 1 ) cannot combine with two pulses to form any false command. This example will be referred to below by sentences enclosed in brackets. As mentioned earlier, it is convenient to make all the time spacings of a discrete code integral multiples of the discrete command tolerance T, in order to avoid overlapping problems between different commands. This being so, one can represent the various time spacings with the in- tegers 1, 2, 3, ■ • ■ ; thej'th n-pulse command is represented by an (n — 1)- dimensional vector of integers (ii, t'^, ■ ■ ■, t^-x). [Specifically, the first command is given by the pair of integers {t\, ti) and the second com- mand by ((i^, ^2^^)]. The one-stage coding problem for discrete commands can now be stated in mathematical terms. Assume that one has k distinct n-pulse commands. All these commands are effective against {n — 2) false pulses [in the sense discussed above] if and only if the following kn{n — l)/2 integers are all different: MISSILE GUIDANCE CODES 977 t/ fori = 1, 2, -■ ■, n - 1 undj = 1, 2, •■ ■, t; ti' + ti+i.' iovi = 1,2, • • • , 71 - 2 and ;" - 1,2, • ■ ■ , A:; i;«/ forj= 1,2, •■■,k. [In our specific problem, we require that the six integers fi\ k , h + (■• , (}', ti, k' + t2^ all be different.] The theorem can I)c proved by indirect reasoning. Suppose that (n — 2) false pulses have combined with two true pulses to form a false command. Then the spacing to between the two true pulses must be equal to more than one of the Jai(n - l)/2 integers listed above (the set of all possible spacings between pairs of pulses in the k commands). Fcr, if (o were equal to only one of these integers, the only command that could be foimed with the aid of these two true pulses would be the correct command. Conversely, if two of these integers are the same, it is easy to construct a false command using (n - 2) properly spaced false pulses. [For example, if the two commands are (3, 8) and (2, 6), then the second command can be falsely formed from the first command by placing an extra pulse two time units after the second pulse in the first command. In this case, the six integers are 3, 8, 11, 2, 6, 8, and h is equal to 8.] If one allows the integers t/ to be arbitrarily large, there is no diffi- culty in discovermg suitable codes. [For example, (31, 73) and (9, 45).] However, equipment and time restrictions usually make it desnable to keep all the commands as short as possible (measured from first to last pulse). Therefore, one may pose the following interesting mathematical problems : i. For a given /: and n, what is the minimum possible length of the longest command under the restrictions above? ii. Are there any (simple and practical) methods for constructing codes w^ith minimum command length (or a little longer)? Neither of the above two problems has been solved; lower bounds can (in a limited way) be set for the first, and the second has largely been investigated by trial and error. The problem is similar to the eight queens problem* in chess, but with additional restrictions. More gener- * The eight queens problem consists of placing eight queens on the chess board BO that no queen can capture any other along a row, column, or diagonal. A specific Code can be characterized by a pair of integers {a, b) ; this denotes a position on a generalized chessboard (not restricted to the eight-by-eight size). 978 THIO HELL SYHTKM TECHNICAL JOUKNAL, JULY 1 9()0 ally, it appears to be a problem in partitions in the theory of num- bers. A general lower bound L for the minimum possible length of the long- est command is given by kn{n — l)/2. However, this bound cannot always be achieved even for three-pulse codes. For a three-pulse code, it is true that If the longest command length is equal to Zk^ the set of mtegcrs tj(i = 1, 2;j ^ 1, 2, . ■ ., k), h' + tAj = 1,2, ■■■, k) is a rearrangement of the set of integers (1, 2, ■ ■ •, 3/i;). Therefore, the sum of the two sides of the above equation is 3A(3/.; + l)/2, and the sum of one side alone is 3/r(3/v + l)/4. But this last quantily is an integer if and only if ^: = (mod 4) or k = 1 (mod 4). In other words, '6k is a lower bound L when k = 1, 4, 5, 8, 9, 12, 13, - ■ ■, and Sk + 1 is a lower bound L for all other k. 2.2 Some Typical One-Stage Encodings We now list specific discrete encodings for .several values of /: and n. For the three-pulse codes the lower bound L for the longest delay line needed has actually been achieved for k = 1 (1) 10. The first number gives the time .spacing between the first and second pulses, and the second number the time spacing between the second and third pulses: Typical minimum-length discrete- command three-pulse encoding.s (1.5) (3,4) (4.6) (1,7) (2,3) (1,9) (3,8) (5,7) (2,4) (3,12) (5,9) (2,11) (4,6) (1,7) (4,15) (2,16) (5,12) (3,8) (1,9) (6,7) (3,19) (5,16) (7,13) (6,12) (2,15) (4,10) (1,8) (1,23) (2,11) (3,18) (4,10) (5,15) (6,16) (7,12) (8,9) a, 26) (3,22) (9,15) (2,21) (6,14) (7,12) (10,8) (4,13) (5,11) (5,26) (14,16) (2,27) (8,20) (4,21) (9,15) (1,22) (7,12) (3,10) (6,11) Undoubtedly this list could be indefinitely extended, since it is easy to discover many different encodings for any k which have the same length for a maximum -length command. Unfortunately, an analogous method for impnmng the lower bound L does not exist for n > 3. As n increases, it becomes more difficult to keep the minimum delay line small, and kn(n — l)/2 becomes a very unrealistic lower bound. k L 2 7 3 U) 4 12 5 15 6 19 7 22 8 24 9 27 10 31 MISSILE (.;ril)AXCE CODMR 1)79 The tables below list representative discrete-command four-, five- and six -pulse encodings; the reader is invited to find an encoding with a smaller L' if he can {U denotes the minimum command length that has been achieved, but it may not be the true minimum) : Typical discrete-command four-pulse encodings A; L L' 2 12 13 3 18 21 4 24 27 5 30 31 (2,5,6) (3,1,8) (1,5,12) (2,8,11) (3,4,9) (1,11,15) (2,6,17) (3,7,14) (4,5,13) (2,20,9) (3,14,13) (4,8,16) (5,10,11) (6,1,18) k L L' Typical diacrete-command five-pulse encodings 2 3 20 30 25 38 (1,8,3,13) (2,5,10,4) (1,5,12,20) (2,8,11,14) (3,4,9,15) 30 45 Typical discrete-command six-pulse encodings (1,8,3,13,20) (2,5,10,4,18) If encodings not given in these tables are desired, it should be possible to use a high-speed digital computer to search through a large number of encodings (either systematically or at random) and print out the minimum-length encoduig that it tmds. Unless an algorithm for comput- ing encodings is found, this is the only practical method available. 2.3 A General Class of Discrete Codes As noted hi Section 2.2, the length of the longest conmiand ui- creases rapidly with n, the number of pulses in the command. This, of course, is the price that one pays for protecting oneself against (n — 2) false pulses aiTanged in any pattei'n whatever. One can always reduce the code length by i-educing the protection; that is, construct minimum- length n-pulsc codes that protect against (« — 1) or fewer pulses (i = 3, 4, 5, ■ ■ •, n — 1). The following formulation of the problem is more realistic. Suppose that one wishes protection against 7n false pulses com- bining with (n — m) pulses in any command. i. IIow does one construct H-pulse codes [n > m + 2), keeping the length L of the longest command as short as possible? ii. If power is no limitation (any n can be used within reason), for what value of n is L minimized? No general solution to either of these proljlems is known. This section presents typical encodings for a few of the simplest codes, which were found by trial-and-error methods. The simplest problem in this class is the construction of a four-pulse 980 THE BKLL SYSTEM TECHNICAL JOUKNAL, JULY 1900 code invulnerable to a single false pulse. It can be proved (by the method used in Section 2.2) that, in order for a four-pulse, A;-command code to be invulnerable to one false pulse the following 4/v- integer-pairs must all be different: forj = 1, 2, •■■,k. As before, a lower bound L for the length of the longest command can be obtained. There is one integer -pair (1,1) which sums to 2; there are two more which sum to 3, and in general there are n(n — l)/2 with sums less than or equal to n. Therefore, a lower bound L is given by the smallest value of n satisfying 4A ^ n(n — l)/2. Most of the specific discrete encodings listed below actually achieve this bound; the ones that exceed it by one are marked with an asterisk : k L Typical four-pulae encodings invulnerable to one false pulae a, 1,2) (1,3,1) (4,1,1) (1,4,2) (1,3,1) (1,6,2) (1,5,3) (2,1,2) (1,2,2) (2,4,1) (3,2,3) (2,5,1) (2,2,5) (2,1,3) (1,1,2) (4,2,1) (1,2,4) (3,3,2) (3,2,1) (1,2,4) (4,2,1) (4,2,1) (2,5,1)* (3,2,3) (7,1,1) (1,3,1) (1,3,4) (2,3,1)* For moderate values of k, the minimum length has been reduced more than 50 per cent by adding one more pulse to the code. In order to construct a five-pulse /c-command code that is invulnerable to two false pulses, it can be shown (by the method used in Section 2.2) that the following Wk integer-pairs must all be different: (h^h'), {tJ,tJ), (V,//), ik' + k', k'), ik' + h\ U'), {h\ k' + V), (k\ k' + ti), {k\ k' + k' + U'), (k' + k\ k' + k'), ik' + k' + k\ k') iovj = 1,2, ■■',k. The lower bound L is given by the smallest value of n satisfying lO/c ^ n{n — 1 ) /2. Three typical encodings are given below ; it it believed that they are the shortest ones possible : Typical five-pulae encodings invulnerable to two false pulses (1,2,2,1) (2,3,1,2) (3,3,1,4) (1,3.4,1) (2,2,1,6) (1,7,1,2) MISSILE GUIDANCE CODES 981 In order to construct a five-pulse fc-command code that is invulnerable to one false pulse, it can be shown that the following 5k integer-triples must all be different: (ti, W, h'), (M , is , U ), (// + k\ h\ tj), {k\ uj + h\ u'), (A\ t,\ tj + (/■) for J = 1,2, ••■,1: The lower bound L is given by the smallest value of n satisfying bk ^ n{n — l)(n - 2)/6. A few typical encodings (believed to be minimum length) are given below: it L Typical five-pulse eocodings invulnerable to one false pulse (1,1,2,1) (1,1,3.1) (1,1,3,1) (1,1,3,1) (2,1,1,2) (2,1,1,2) (2,1,1,2) (1,3,2,1) (1,3,2,1) (2,2,1,2) As mentioned before, these tables can be extended with the aid of a high-speed digital computer. The following table summarizes the known behavior of one-stage dis- crete-command codes. It records the shortest known length of the long- est command ; most of these lengths are believed to be the smallest ones achievable. It is evident that one can often reduce this length quite markedly by adding pulses to the code, and that the savings are likely to be greater as the number of commands increases: Codes Invuloerable to One False Pulse Codes Invulnerable to Two False Pulses Numbe r of pulses k 3 4 5 1 2 3 4 5 6 3 7 10 12 15 19 4 5 5 6 6 7 7 7 8 — 8 — Number of pulses k 4 5 6 1 2 3 4 7 13 21 27 6 — 9 — 11 — III, TWO-STAGE CODES The single-stage codes discussed in Section II should prove quite use- ful to the designer of missile guidance equipment. However, they suffer from the drawback of trying to do too many things at once. Sometimes it is more reasonable 1o lireak the decoding job up into several smaller jobs that are performed in sequence. Thus, the output puise resulting 982 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 from one decoding operation becomes an input pulse to the next decoding operation. An important advantage of such a break-up is that at least part of the security function of the code can be separated from the command function. This means that one can build in between-missile security without behig forced to change the command codes from one missile to the next. Furthermore, the between-missile security codes can be used to mcrease the search time of a knowlcdgealile enemy for the correct code. A second advantage is greater simplicity of both codes and compo- nents. If one needs to protect against (say) as many as four false pulses, it is not easy to find optimum single-stage codes, and the required de- lay lines may not be available. Multistage codes provide additional designs that may be easier to instrument. Balanced against this, of course, may be an increase in the number of components needed. Multistage discrete-command codes are those that use a delay line and multiple .\nd circuit decoding mechanism (see Section I) at each stage. For simplicity, let us restrict ourselves to two-stage codes, which possess most of the potential advantages of multistage codes. Let the symbol i \ j denote a two-stage code containing ij pulses : the first stage decodes j' clusters of i pulses each and the second stage decodes the cluster of J output pulses emitted by the first-stage and circuit. Usually the command part of the code occurs at the second stage. However, it makes no difference whatever which stage it is assigned to: an i \ j security-command code has precisely the same invulnerability to false pulses as does a j | i ecmimand-security code. Let us assume for convenience that the commands are always contained in the second stage. 3.1 An Upper Bound for the Protection How much protection can an i \ j code give against false pulses? As- .sume that the two stages are each designed according to single-stage rules, so that they are in\'uhierab]e to (i — 2) and (j — 2) false pulses, respectively. Then an upper bound to the inmiber of false pulses that can be arranged in any pattern whatever with the ij true pulses wilh- out forming a false (or repeated) command is M = mm [i(j - 1) - l,j(i - 1) - 1]. The first term arises because false pulses can be arranged in (,/ — 1) groups of i false pulses each, and these gi'oups can be combined with one true i-pulse group to form a false command. The second term arises MISSILE GUIDANCE CODES 983 JJ I I I I TYPICAL ENCODING u FIRST-TERM ERROR . Lfj-1)-1 = 3 J_i_L SECOND-TERM ERROR Fig. 2 — Firat- and second-term error for 2 | 3 code. because false pulses can be arranged in j groups of (i — 1) false pulses each, augmented by j true pulses, one from each of the .7 groups in the correct code. This is illustrated in Fig. 2 for the 2 j 3 code. Although M is the same for lioth an i \ j and aj\i code, the two er- rors are not symmetric. Note that the first type of error can result in a false command, but the second type of error can only repeat the sarne command slightly earlier or later in time. The second error is likely to be less serious, and in fact can be eliminated by introducing a device that prevents repetition of the same command within a specified period of time. Accordingly, in the rest of this section we emphasize codes that are protected against i(j - 1) - 1 false pulses combming with true pulses to form a different false command. For i, j greater than or equal to two, the maximum possible protec- tion is always less than that achievable with a smgle-stage code using ij pulses. Thus, these codes are somewhat comparable to the reduced- protection shigle-stage codes discussed in Section II. 3.2 Methods for Combining Securitij and Command Codes In order to actually achieve the upper bound of the protection, one must be a little careful when combining the two .stages of the code. There are many ways of doing this, and the choice of a particular method depends upon the ease of instrumentation. For example, consider the following alternatives for the 2 ) 3 code (see Fig. 3). 3.2.1 Short Command Codes, Long Security Codes Let the three-pulse commands be encoded according to the methods in Section II. The longest command will be approximately Sk if there are k different commands. The two pulses forming the security code should bo more than Qk apart in order to avoid the possibility of three false pulses forming a false command. This design is probably the easiest to instrument. 984 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 _.- COMMAND ENCODING -^^ v^^ — I r — t 1 I I I I I I (a) SECURITY ENCODING COMMAND ENCODING (b) [ I I I L4 SECURITY ENCODING COMMAND ENCODING Ccj JJ u u SECURITY ENCODING Fig. 3 — Methods for combining security and command codes: (a) short com- mand codes, long security codes: (b) interleaved security and command codes; (c) long command codes, short security codes. 3.2.2 Interleaved Security and Command Codes Let the spacing between the two-pulse security codes consist of odd integers, and encode the three-pulse commands in even integers using the methods discussed in Section II. To iUustrate: if four commands are to be sent, let them be (2, 18), {6, 16), (10, 14) and (4, 8). More se- curity and command codes can be ea-sily added. 3.2.3 Long Command Codes, Short Security Codes Let the spacing between the two-pulse security codes be given by the integers 1, 2, ■ ■ ■ , m. Encode the three-pulse commands in multiples of 2m (or greater) according to the methods of Section 11. This is likely to be the most difficult design to instrument. These alternatives all provide the maximum possible protection ; four false pulses are needed to form a false command, and three false pulses are needed to shift the true command in time. The first and third alternatives are very easy to encode for any values of i and J (if the necessary single-stage codes are available), and are not discussed further. False pulses that combine with true pulses to form false MISSILE GUIDANCE CODES 985 security codes cannot possibly form false commands as well, because these false pidses are either too far from or too close to the other true pulses to do the job. Fretiueiitly the longest delay line is somewhat longer for these alternatives than it would be if an interleaved code were used. Accordingly, we devote the rest of this part of the paper to the construc- tion of interleaved codes. 3.3 The Problem of Interleaving Security and Command Codes This section discusses the prol)lem of interleaving z-pulse security codes with ^-pidse command codes in such a way that one is protected again.st i(j - 1) - 1 ftilse pulses forming a false command. Probably the simplest way to interleave the codes is to reserve the integers /(i), 2f(i), 3/(i), ■ ■ ■ for the command codes. Then one can coJistruct mini- mum-length command codes uivulnerable to (j - 2) false input pulses according to the methods discussed in Section II. [It will be shown later that the minimum possible value for/(0 is i.] The interleaving problem is now reduced to the problem of selecting the security code spacings so that one is protected against i(j - 1) - 1 false pulses. The following sections present two restrictions on the secu- rity codes and show that these restrictions are sufficient to guarantee this protection. No claim is made that this is the only way to interleave codes; however, the resulting codes do have optimum properties, which are described later. 3.3.1 Two Restrictions on the Security Code The security code spacings (ti,t2, ■■• ■ ^-i) should be chosen in such a way that (a) no set of (i - 2) false pulses can combine with two true pulses to form a false security code, and (b) none of the i{i - 1) integers ±tk, k = 1,2, ■■■ ,i - I; Mtk + h+i), k = \,2, ■■- ,i-2; ±{ti + t2+ ■•■ + /.■-!) should be a multiple of /(i) [that is, equal to mod/(0]. The first restriction states that security codes should be single-stage codes consisting of only one command (see Section II). The second re- striction accomplishes two goals. Fh-st, since none of the integers h , 986 THE BELL SYSTEM TECHNICAL JOURNAL, JULY I9G0 t t _|J U L i i II |- 't.-t.) ^^ I I i i j i i I I L = i I t _LLi U UJ LL t. Fig. 4 — Six false security codes for a three-pulse code. ti -\- t-i , • ■ • , ii + t-> -\- ' ■ ■ -\- ti-i is a multiple of /(i), any i \ j code will consist of the full set of ij pulses. (Any pulse serving two functions at the same time is a natural candidate for a false pulse.) Second, the above set of mtegers lists the starting times of all the false security codes con- sisting of (i — 1) false pulses and one true pulse (relative to the starting time of the true security code). For example, for a three-pulse security code, the six false security codes are shown in Fig. 4. Now, consider what happens if one of the above spacings is a multiple oif(i). One of the command code spacings is formed by the false security code corresponding to this spacing and one of the true security codes; the other (j — 2) command spacings are formed by i(j — 2) false pulses. But (i — 1) + i(j — 2) ^ i(j — 1) — 1, which is the number of false pulses we wish to protect against. The 3 | 4 code illustrates this point (see Fig. 5). It is shown in Section 3.3.2 that codes .satisfying these restrictions are protected against i(j — 1 ) — 1 false pulses, and that the mmimum possi- ble value oi f(i) is i. 3.3.2 Proof That These Restrictions Insure Protection Given these two restrictions, how can false commands be formed? Each security code in the false command can include at most one true TRUE CODE FALSE CODE I II I II LU LLL I ■■III ■■■ ■■■ ■■III ■■■ ■■■ ■■III ■■■ ■■■ ■ ■ I i_i ■ ■_■ J — ■ ■ k *~ ALL COMMAND CODE SPACINGS ft, +13) = A MULTIPLE OF f(0 IN BOTH COOES ^ ' 2' ^ ^ ARE MULTIPLES OF f(L) Pig. 5 — A 3 I 4 code with spacing a multiple of /(t). MISSILE GUIDANCE CODES 987 pulse, because of restrictions (a) and (b). [There is one exception: a false command can be constructed out of one true security code and (j - I) false security codes of i pulses each.] Furthermore, ij pulses are needed for the false command, according to restriction (b). Therefore, if we can show that the false command contains at most i true pulses (one in each of i different false security codes), then we are done, for the (ij _ {) or more false pulses needed to make up the balance of the false command will exceed i(j - 1 ) - 1, the number of false pulses we wish to protect agamst. Since all the true command spacings are multiples of /(z), it is sufficient to show that one can select at most i false security codes consisting of one true pulse and (i - 1 ) false pulses each, which arc all spaced f(i) apart from each other. In the preceding section, we listed all the i(i - 1) possible false se- curity code startmg times (relative to the true security code). If we can show that exactly i of these times are equal to a (mod i), where a = I, 2^ ... ^ i — 1, then we will have proved that at most i different false security codes can have the proper command spacing. Furthermore, we will have proved that/(0 = i; and it is clear that this is the smallest integer it can be. Consider the following arrangement of the i{i - 1) false security code starting times in a matrix with i rows and (i — 1) columns: h,h-\- t2,h^ t2-\- h, , /i + ■ ■ ■ + ^-1 (2,(2 + ^3, ,^, + .-■ + /,_i, - /, /, , /3 + /.. ,/;>+■■■+ ^-1 , -t'l ,-(/! + ^2) /,-! , -t^-2 , -ii.-^ + '/-2), , -(^1 + ■ • ■ + ti-2) -U-,, -(/,^. + ^-i). , -(/2+ ■■• +U-l), -((1+ ■■■ -l-/,-l). If the integers in each row are reduced modulo i, they will be a per- mutation of the integers 1, 2, -■•,«- 1. Weprovcthis by .showing that the opposite conclusion leads to a contradiction. If two integers in a row are both equal to the same integer mod i, then their difference is equal t,o mod i. But their dilTerence is contained elsewhere in the matrix, which contradicts the assumption that no starting times are mod i [restriction (b) aliove]. Since \vc have proved that each row is a per- mutation of the first [i - 1) integers, it is (^ear that the matrix con- sists of i starting tunes equal to a(mod t), a = 1, 2, • • • , (z - 1). 988 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 It is not too difficult to actually fiiid security codes satisfying restric- tion (b). For example, consider the security code (h = 1, (2 ^ 2, ty = 8). We have ±ti= ±1 = 1 mod 4, 3 mod 4; ±^2 =±2 = 2 mod 4, 2 mod 4; i/a = d=3 = 3 mod 4, I mod 4; ±(/i + h) = ztd = 3 mod 4, 1 mod 4; ±(^2 + /s) = ±5 - 1 mod 4, 3 mod 4; ±(^1 + ^2 + /a) = ±6 = 2 mod 4, 2 mod 4. There are exactly four starting times for each of the three values of a. Note that this security code does not satisfy restriction (a), but that (/, = 1, ij = 2 + 4 = 6, /, - 3) does. If i < j m an i \ j two-stage code, the above two restrictions on the construction of security codes should be applied. However, if i > j, then we automatically have more than the minimum protection i(j — 1) — 1 against false pulses — the false command can contain at most ij — j false pulses (ignoring the one exception mentioned above). One can trade off this unnecessary additional protection for a larger set of security codes. To be specific, one can replace the first restriction with (me of the following less stringent restrictions: (a') no set of (i — k) false pulses, for fc = 3, 4, • • ■ , z — 1, can com- bine with k true pulses to form a false security code. These single-stage codes have already been discussed m Section II. For example, if one wishes to construct a 4 | 2 code, then one can u.se security codes that protect against only one false pulse (instead of two, the greatest possible protection). 3.4 Some Typical Interleaved Security and Command Codes The preceding section presented two restrictions on the security code, which guarantee that the resultuig i \j interleaved two-stage code will be protected against i(j — 1 ) — 1 false pulses forming a false command. Nothing, however, was said about the actual construction of such codes. This section presents sample codes for low values of i and j. The command codes of an i [ j code are restricted to the spacings i, 2i, Si, ■ • ■ and are constructed according to the methods discussed in Section II. The security codes are constructed by trial-and-error methods to satisfy the two restrictions. For i = 2, the odd integers all form se- MISSILE Gl'IDAXCE CODES 989 curity encodings. For i = 3, the pairs (1, 4), (2, 5), (4, 7), (5, 8), ■ ■ ■ and their reverses arc legitmiate security encodings. In general, such encodings must be of the form ((, , /a), where h ^ h and {h , h) equals (1 mod 3, 1 mod 3) or (2 mod 3, 2 mod 3). For i = 4, the triples (1, 5, 9), (2, 1, 6), (1, 6, 3), (2, 3, 6) and (6, 5, 2) are examples of short security encodmgs. In general, these security encodings must be of the form (ii , h , h) where none of the integers ^ , (2 , ^3 > ^ + '2 , '2 + (3 are equal, and {h , (2 , k) is in one of the foUowhig forms: (1 mod 4, 1 mod 4, 1 mod 4); (2 mod 4, 1 mod 4, 2 mod 4); (1 mod 4, 2 mod 4, 3 mod 4) ; (2 mod 4, 3 mod 4, 2 mod 4) ; (3 mod 4, 3 mod 4, 3 mod 4) or (3 mod 4, 2 mod 4, 1 mod 4). These interleaved two-stage codes can be regarded as mmimum-length codes in the following sense : given that the command codes are restricted to the mtegers/(0, 2J{i), Zf{i), ■■■ , then (a) /(?■) is equal to its minimum value i; (b) the longest command code is as short as possible; and (c) the security codes are as short as possible. Assuming that one wishes to protect against a given number of false pulses, which i | j code should one select? The answer depends upon the relative importance of mmimizing the number of pulses ij in the code, and keeping the longest command delay line as short as possible. There are two possible ways to balance tliese factors agamst each other: (a) apply the methods used in one-stage codes (Section II) to the command code ; (b) change the values of both i and j; codes with large i and small j have shorter delay lines and more pulses, while codes with small i and large J have the opposite characteristics. Let us illustrate these ideas with a few simple examples. Assume that we wish to transmit six commands. The 2 | 3 and 4 | 2 codes both provide protection against at most three false pulses. The number of pulses per command is sk and eight, while the maximum delay-line length is 19(2) = 38 and 6(4) = 24, respectively. Suppose that one uses a 2 | 4 code but designs the command code so that it is mvulnerable to one false input pulse (no matter how placed) but not two. Then, referring to Section II, we see that the number of pulses per command is eight and the maximum delay line is 8(2) = 16. How do two-stage codes compare with one-stage codes? The only direct comparison available is the 2 ) 2 code with the four-pulse one-stage code protected against one false pulse: both codes have the same number of pulses and the same protection against false pulses. The length of the longest delay line needed is tabled below for various commands: 990 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1 9C0 Number of commandB 2 3 4 5 6 7 Two-stage code One-stage code 4 5 6 6 8 7 10 8 12 S 14 9 IV. ACKNOWLEDGMENT The author is indebted to W. J. Albersheim for the suggestion that a general study of missile codes be made. He is also indebted to W. L. Roach for a very careful reading of an earlier draft; his suggestions led to many improvements in this paper. APPENDIX Relationship to Error-Correcting Binary Codes There is a certain relationship between the missile guidance one-stage code problem presented in Section II of this paper and the error -correct- ing binary codes that have been extensively studied in information theory. Suppose that one wishes to transmit any one of a large set of messages over a binary channel, and .suppose that there is a pi'obability p that a one will be changed to a zero or a zero to a one in the course of transmission. One can encode the messages ui such a way that every message differs from every other message in at least four places: for example, 100000, 011100, 111 Oil and 000111. (If four messages are to be sent, these are the shortest messages possible.) Note that single errors can be corrected immediately (111111 must be 111011), and double errors can be detected but not corrected (110100 can be either 100000 or 01 1100). In general, one attempts to encode A'^ messages in lengths as short as possilile so that n simultaneous errors in the encoding can be corrected (that is, the original message can be identified). Viewed geometrically, each encoded message has a cluster of closely related correctable mes- sages associated with it (for example, all messages differing from the correct one in only one unit). These clusters are packed as tightly as possible into a binary /i -dimensional space (/*■ is the encoded message length) having a total of 2*" points. When the encoded messages are transmitted, synchronization of some sort must be provided between the transmitter and the receiver in order that the receiver may know when each bhuuy message starts. The message length is kept as short as possible in order to maximize the infcjrmation rate in the chaimel.* The missile guidance one-stage codes of this paper can very easily * For a detailed discUBsion of these error-correcting binary codes, see Slepian.' MISSILE GUIDANCE CODES 991 be repre.sentcd as binary messages: each binary digit corresponds to - time units, and the pulses of the message are represented by ones. For example, the two three-pulse commands (1, C) and (2, 3) become (11000001) and (101001). To make the representation more precise, the shorter messages can be extended with zeros so that all messages are of equal length. There are two differences between the missile guidance single-stage codes and the error-correctmg binary codes; both are discussed in the ])aragraphs below. The first difference is concerned with synchronization, and the second with the shapes of the clusters of correctable messages. A.i Synchronization The error-correcting binary decoder accepts messages in non-over- lapping sets of k digits each ( where /; is the message length ) . This implies that some sort of synchronization between the sender and receiver has been established; otherwise the receiver does not Icnow when to start decoding. This synchronization is not easy to provide in missile com- munications, because of the rapidly changing position of the missile relative to the ground transmitter. Therefore, the missile receiver is arranged to start decoding any time a pulse (that is, a "one") is re- ceived. Some work has been done on self-synchronized codes. For example, Golomb, Ciordon and Welch" have derived upper bounds for the number of /c-digit messages that can be constructed using an /i-digit alphabet. They reriuire that the set of messages have the property that the final (A- - i) digits of any message in the set followed by the first i digits of any message in the set does not form a message in the set. A set of mes- sages with this property automatically provides synchronization; even when the decoder looks at all the intermediate "messages", it recognizes none of them. However, the work described above has not yet been ap- plied to errnr-correcting codes. It is possible, in fact, that self-synchro- nized error-cori-ecting binary codes may be of limited interest to hiforma- tion theorists because of the reduction hi the number of messages per second that can be sent over a channel. However, channel capacity and rate of information flow are not objectives of the missile guidance codes. A. 2 Clusters of Correctable Errors The second difference between the missile codes and Ihe binary codes is the shape of the cluster of correctable errors associated with a given message. The binary code cluster usually consists of those t-digit mes- 992 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 sages that differ in only a few digits (say, one or two) from the true message. The missile code cluster, on the other hand, is neither "close" to the true message nor easy to describe geometrically. It consists of all A;-digit messages that contain ones in n specified places; for example, if 100101 is the message, then 111101, 101101 and 111111 will be decoded as the message. Obviously, the correctable clusters of different messages overlap each other. To separate the clusters as much as possible, the messages are selected so that no member of one cluster with (2n — 2) or fewer ones is a member of any other cluster. [This is simply a restate- ment of the requirement that (?i — 2) false pulses added to any command cannot possibly form a false connnand.] In order to visualize these correctable clusters, it is convenient to transform from the A;-dimonsional discrete binary space of messages to the (n — 1) -dimensional continuous space of times between any set of n pulses (true or otherwise). Let us examine the shape of this cluster a little more precisely for n equal to low values. For n = 2, the cluster is a line segment 2r units long* centered on the correct spacing ti . For ti = 3, the set of three-pulse messages that will be decoded as a command (ti , tz) is contained in the polygon of Fig. 6. This figure corresponds to a delay line that delays the first pulse for a time h -\- (2 , the second pulse for a time ^2 , and the third pulse not at all. A set of pulses with original spacing (ti , (») will be brought into exact coincidence by this delay line. The upper right corner of the square has been sawed off because, for original spacings (ti , (2) in this region, /i + ^2 > ^x + ^2 + t, and there- fore the first and third pulses will be separated by more than t after passing through the delay line. For n = 4, all decodable messages are contained in the three-dimen- ■r — r — *] ■^t, U\ti Fig. 6 — Polygon containing set of three-pulse messageB that will be decoded as a command (d , (a). * The quantity t is the discrete command tolerance defined in Section I. In order for a command to be recognized, the time between the earliest and latest of the n pulses arriving at the and gate must be less than t. MISSILE GUIDANCE CODES 993 Fig. 7 — Polytope containing all decodable messages for n == 4. sional polytope of Fig. 7. This figure corresponds to a delay line that de- lays the first pulse h -\- (2 -\- h , the second pulse tz + h , the third pulse ti , and the fourth pulse not at all. For 7i ^ 4, it can be shown that these polytopcs can be packed in such a way as to fill the space completely; it is probably not difficult to show that this is true for arbitrary n. The ratio of the volume of the (n — 1) -dimensional polytope to the (n — 1) -dimensional hypercube of side 2t (which encloses it) is [ n(n - Dx^-'d - .r) dx = Jo n + 1 2" This integral is equal to the probability that n points drawn at random from a uniform distribution on (0, 1 ) will all be located within one-half of each other. To what use can these polytopes be put? In the bmary code problem, one places a message at the center of each polytope and packs them into the space as tightly as possible. However, in the missile guidance prob- lem the messages cannot be packed so closely. Consider an n-pulse com- mand plus (n ~ 2) false pulses. There are {2n - 2)\/n\{n - 2)! possi- ble ways of choosing an n-pulse group, and none of these groups (except for the one consisting of n true pulses) is allowed to lie withhi any poly- tope centered on a true command. The polytopes must be very sparsely scattered through (n — 1) -space. Let us assume that the true commands are transmitted with timing errors that are very small with respect to the discrete command toler- ance T. (This is ordinarily true in practice; if it were not, some of the commands might not be received by the missile.) Then, if the true com- 994 THE BELL SYSTEM TECHNICAL JOURNAL, JULY 1960 mands are encoded according to the niles stated in Section II, any false command consisting of (n — 2) or fewer false pulses will have at least one spacing Ihat is at least r dilTcrcnt from any true ciimmand spacing. But the polytope centered on ajiy true command is bounded by the hypcreulse of side 2r; therefore the false command cannot be decoded as any true command. In general, if the maximum timing error is e, the commands should be encoded in uitegral multiples of a liasic time- quantum T + e. It is not possible to relax the eneodmg rules of Section II to allow for the fact that we arc dealing with polytopes rather than hypercubes. The reason for this is simple: the polytope intersects each of the 2''"~" faces of the hypercube. REFERENCES 1. Slepiim, D., A Class of Binary Signaling Alphabets, B.S.T.J., 35, 1956, p. 203. 2. Golomli, S, W., Gordon, B. and Welch, L. P., Comma-Free Codes, Can. J. Math., 10, 1958, p, 202.